\section{Jednorázové a fail-stop podpisové schémy}

Jednorázové podpisové schémy, ako už ich názov napovedá, slúžia na
podpísanie práve jednej správy. Ich bezpečnosť je v prípade viacnásobného
podpisovania ohrozená. Načo sú nám teda takéto podpisové schémy? Zatiaľ to
vyzerá tak, že sú iba menej výhodné. Existujú však dôvody, prečo sa zaoberať
aj takýmito zjavne ``okrátenými'' podpisovými schémami.

Ich hlavná výhoda bude spočívať v jednoduchších predpokladoch pri dôkaze
bezpečnosti. Kým pri bežných podpisových schémach sme stavali na
tažkosti istých matematických problémov (RSA, dlog, Diffie-Hellman),
pri jednorázových schémach nám bude stačiť napríklad jednosmernosť
hašovacej funkcie.\footnote{Už aj toto je pomerne náročný predpoklad,
    keďže nevieme povedať veľa o existencii one-way funkcií.}
Druhou výhodou môže byť rýchlosť -- zrejme je jednoduchšie hašovať hodnoty
ako napríklad umocňovať.
Treťou výhodou (i keď skôr teoretickou) je možnosť odolať kvantovým
výpočtom -- pre väčsinu používaných ťažkých problémov sú známe kvantové
algoritmy, ktoré ich efektívne počítajú. Pre invertovanie hašovacích
funkcií ale takéto algoritmy nie sú známe.

Otázka teda môže znieť, že či jednorázovosť je až taká obmedzujúca
vlastnosť. Môžeme napríklad uvažovať komunikáciu s bankou a podpisovanie
prevodných príkazov. Je jednoducho predstaviteľné, že
bežný človek za mesiac nespraví viac ako povedzme 20 príkazov.
Preto môžeme použiť
niečo ako pohľad z opačnej strany -- namiesto toho, aby sme navrhovali
podpisové schémy na polynomiálny počet podpísaných správ,
môžeme sa snažiť navrhnúť schémy na jednorázové podpisy a tie potom
rozšíriť nejakým spôsobom pre viac správ.

Jednorázovú podpisovou schému formálne definujeme veľmi podobne ako bežné
podpisové schémy

\begin{definicia}[Jednorázová podpisová schéma]
    je trojica algoritmov 
    $\langle Gen, Sign_{sk}, Verify_{pk} \rangle$ kde
    $Gen(1^k) \rightarrow \langle pk, sk \rangle$ je generátor kľúčov,
    $Sign_{sk}(m) \rightarrow \sigma$ je podpisovací algoritmus a
    $Verify_{pk}(m,\sigma) \rightarrow \{0,1\}$ je overovací algoritmus.
\end{definicia}

Pojem bezpečnosti takejto schémy si upravíme na jednu správu.
\begin{definicia}[Bezpečnosť]
    Uvažujme útočníka ako PPT algoritmus, ktorý má navyše k dispozícii
    orákulum $Sig_{sk}$. Útočník sa môže raz opýtať orákula na podpis
    $\sigma$ správy $m$ a jeho cieľom je zostrojiť
    správu $m' \ne m$ a k nej platný podpis $\sigma'$.
    Budeme hovoriť, že schéma je bezpečná ak pravdepodobnosť,
    že ľubovoľný útočník uspeje (t.j. nájde $(m',\sigma')$), je zanedbateľná.
\end{definicia}

\subsection{Lamportova schéma}

Uvažujme, že máme funkciu $h: X \rightarrow Y$, ktorá je jednosmerná.
Budeme podpisovať správy $m$ fixnej veľkosti $|m|=n$. Toto samo o sebe nie
je žiadny problém, ak uvážime, že budeme podpisovať len haš správy, ktorý je
fixnej veľkosti.

Generovanie kľúča bude vyzerať nasledovne:

%%% {{{ proc GenLamport
\begin{procedure}[H]
    \caption{GenLamport($n$)}
    \For{$i:=1$ \KwTo $n$}{
        $x_{i,0} \inr X$\;
        $x_{i,1} \inr X$\;
        $y_{i,0} \assign h(x_{i,0})$\;
        $y_{i,1} \assign h(x_{i,1})$\;
    }
    \Return $sk=\langle x_{1,0},x_{1,1},\ldots,x_{n,0},x_{n,1}\rangle,\quad
             pk=\langle y_{1,0},y_{1,1},\ldots,y_{n,0},y_{n,1} \rangle$\;
\end{procedure}
%%% }}}

Čitateľ už môže tušiť, ako budeme podpisovať správu -- jednoducho postupne
podpíšeme všetky jej bity tým, že zverejníme príslušnú časť súkromného
kľúča.

%%% {{{ SignLamport
\begin{procedure}[H]
    \caption{SignLamport($m$)}
    \For{$i:=1$ \KwTo $n$}{
        $\sigma_i \assign x_{i, m_i}$\;
    }
    \Return $\sigma = \langle \sigma_1, \ldots, \sigma_n \rangle$
\end{procedure}
%%% }}}

Overovanie spočíva v overení každého podpísaného bitu správy.

%%% {{{ VerifyLamport
\begin{procedure}[H]
    \caption{VerifyLamport($m, \sigma$)}
    // $\sigma_i = x_{i, m_i}$ \;
    \For{$i:=1$ \KwTo $n$}{
        \If{$h(\sigma_i) \ne y_{i, m_i}$}{
            \Return reject\;
        }
    }
    \Return accept\;
\end{procedure}
%%% }}}

Bezpečnosť schémy je založená na nasledujúcom pozorovaní:
Aby bol útočník k správe $m$ a jej podpisu $\sigma$ vygenerovať
falošnú správu $m' \ne m$ a jej podpis $\sigma'$, musel by byť schopný
vygenerovať $x_{i,b}$ pre nejakú novú dvojicu $(i,b)$.
To ale znamená invertovať niektorú hodnotu $y_{i,b}$ verejnej
hašovacej funkcie $h$ a to predpokladáme, že je možné iba so zanedbateľnou
pravdepodobnosťou.

Na druhej strane, schéma je evidentne jednorázová.
Až na špeciálny prípad, keď sú podpísané dve správy $m_1,m_2$ líšiace
sa v práve jednom bite (vtedy si útočník nepomôže), vieme kombinovať
jednotlivé bity podpisov a podpísať inú správu. V prípade, že
podpisujeme haš hodnotu, je navyše očakávané, že správy sa budú líšiť
na zhruba polovici bitov.

\medskip
Uvažujme teraz praktické aspekty používania takejto schémy. Podpisujme
haš, napríklad výstup z funkcie SHA-256. Ďalej predpokladajme, že
$|X|=|Y|=256 \unit{bit}$. Potom dostávame pre súkromný kľúč veľkosť
$|sk|=2*256*256 \unit{bit} =16 \unit{kB}$. Verejný kľúč je rovnako dlhý, čiže
$|pk|=16 \unit{kB}$ a podpis má polovičnú dĺžku kľúčov, čiže $|\sigma|=8
\unit{kB}$.
V porovnaní napríklad s RSA je to výrazne horšie. Bolo by teda dobré
nejakým spôsobom skrátiť kľúče.

\subsubsection{Skrátenie súkromného kľúča}

Namiesto celého kľúča $(x_{1,0}, x_{1,1},
\ldots x_{n,1})$ si budeme pamätať iba náhodné $x \inr X$ -- seed pre
pseudonáhodý generátor, ktorý postupne vygeneruje dané hodnoty
$x_{i,b}$. Problém v tomto prípade je ďalší predpoklad -- bezpečnost
pseudonáhodného generátora (t.j. že z niektorých hodnôt postupnosti
$x_{1,0}, \ldots, x_{n,1}$ nevieme efektívne vypočítať žiadnu ďalšiu -
to by bolo ekvivalentné zlomeniu podpisovej schémy).

\subsubsection{Skrátenie verejného kľúča}
Namiesto celého kľúča zverejníme iba haš
$y=H(y_{1,0},y_{1,1},\ldots,y_{n,1})$. Tým pádom ale pri podpisovaní
musíme uviesť aj všetky hodnoty $y$, aby si to overovateľ mohol
overiť. Po chvíli zamyslenia sa ale môžeme pozorovať, že na overenie
stačí poslať tie hodnoty $y_{i,b}$, ktoré si overovateľ nemôže
spočítať. Tieto sú presne negácie bitov správy a teda nám stačí poslať
iba polovicu hodnôt $y_{i,b}$. Podpis sa nám tým predĺži na $16
\unit{kB}$.

\subsubsection{Merkleho konštrukcia}
Ďalši nezávislú možnosť ako skrátiť dĺžku postupnosti vymyslel
Merkle. Hlavnou pointou bude pridať akúsi formu checksumu -- počtu
nulových bitov správy. Potom budeme pri podpisovaní podpisovať iba
jednotkové bity, čím ušetríme v priemernom prípade takmer polovicu bitov
(čiže v našom prípade $|\sigma| \approx 4 \unit{kB}$).

Presnejšie, majme správu dĺžky $l$. K nej pridáme checksum dĺžky
$\lceil \log l \rceil$ a na výsledok dĺžky $n=l+\lceil \log l \rceil$
použijeme podpis, kde podpíšeme iba jednotkové bity.

V prvom rade by sme mali ukázať, že takáto zmena nepokazí bezpečnosť
schémy. Majme preto známu správu $m$ s podpisom $\sigma$ a
predpokladajme, že sa útočník snaží vyrobiť $m'$.
Ak existuje bit číslo $i$ taký, že $m_i=0$ a platilo by $m'_i=1$, tak sa dostávame
do známej situácie, kedy útočník musí vyrobiť platný vzor pre $y_{i,1}$.
Ošemetná situácia ale nastáva, ak máme $i$-ty bit $m_i=1$ a útočník ho zmení
na nulu. V tomto prípade totiž nemusí nič podvrhnúť, lebo pre nulový
bit nemusí nič uviesť. Zachráni nás však checksuma -- totiž, ak zmenšíme
celkový počet jednotiek v správe (a to jediné nám ostáva, ak nemáme
nablyšťanú guľu na lámanie one-way funkcie), vznikne nám aspoň jedna
jednotka na doteraz neodhalenom mieste. Nie je totiž možné, aby sme
po pričítaní čísla k checksume dostali checksumu pozostávajúci iba zo
známych bitov -- to by znamenalo, že daná checksuma používa iba
niektoré jednotky z pôvodnej, lenže to je v spore s tým, že je
väčšia. Preto aj v tomto prípade musí útočník úspešne nájsť vzor
jednosmernej fukncie a schéma ostáva naďalej bezpečná.

Ďalšou príjemnou vlastnosťou tejto úpravy je automatické zmenšenie
súkromného a verejného kľúča na polovicu - vôbec nepotrebujeme
generovať $x_{i,0}$ a $y_{i,0}$.

\subsection{Merkleho stromy}

Ako sme už písali, jedna z možností ako ``vylepšiť'' našu schému
je nájsť spôsob, ako z jednorazovej schémy spraviť schému na pár
použití. Jednoduchý spôsob je vygenerovať potrebný počet inštancií
schémy a zverejniť príslušné verejné kľúče. Problém tohoto prístupu je
čisto praktický -- musíme zverejniť veľmi dlhý verejný kľúč (všetky
verejné kľúče). V prípade, že máme napríklad jednu centrálnu autoritu,
ktorá vydáva súkromné kľúče a na svojej stránke zverejňuje všetky
verejné kľúče, to môže robiť isté problémy.

Preto by sme chceli akýmsi spôsobom zredukovať údaje o všetkých
verejných kľúčoch do nejakého odtlačku. Môžeme to spraviť rekurzvívne
-- označme si $H_{i,j}$ ako odtlačok všetkých kľúčov v intervale 
$\left<i,j\right>$.
Potom môžeme definovať rekurzívne $H_{l,r}=h(H_{l,m} || H_{m+1,r})$ kde
$m$ je stred medzi $l$ a $r$, čiže $m=\lfloor (l+r)/2 \rfloor$ a
$h$ je hašovacia funkcia. Takýmto spôsobom môžeme vybudovať celý
strom.
\begin{figure}[h]
    \centering
    \includegraphics{img/06/merkle.1.mps}
    \caption{Merkleho strom}
    \label{fig:merkle}
\end{figure}

Použitie bude nasledovné: Ako verejný kľúč zverejníme $H_{1,n}$. Toto je
malá hodnota a preto sa dobre distribuuje. Následne, predpokladajme, že
chceme použiť na podpisovanie kľúč číslo $x$. Na to, aby sme mohli overiť
podpis potrebujeme vedieť overiť celú cestu od kľúča $x$ ku koreňu. Toto
môžeme spraviť nasledovne -- zverejníme hodnotu pre každého súrodenca
nejakého vrcholu na ceste (týchto súrodencov si označíme ako
``autentifikačnú cestu'').
Ak totiž vieme vypočítať hodnotu vrchola na ceste a poznáme
súrodenca, tak vieme vypočítať hodnotu otca daného vrcholu.
Teda ak vieme hodnotu $pk_x$ a poznáme hodnoty všetkých súrodencov po ceste ku
koreňu, vieme postupne vypočítať hodnotu až ku koreňu. Následne stačí
overiť, či vypočítaná hodnota sedí so zverejnenou hodnotou $H_{1,n}$.

\begin{figure}[h]
    \centering
    \includegraphics{img/06/merkle.2.mps}
    \caption{Autentizačná cesta pre kľúč č.4}
\end{figure}

Pri tomto riešení teda pri jednom podpise musíme zverejniť popri podpise aj
celú autentiazačnú cestu, jej dĺžka je logaritmická od počtu kľúčov, ktoré
chceme používať. Je teda len na nás, či obetujeme zväčšenie podpisu na to,
aby sme mohli mať menší verejný kľúč.

Ďalšia zaujímavá otázka je výpočet autentifikačnej cesty. Vo všeobecnosti
pri veľkom strome totiž vypočítať jednotlivé potrebné hodnoty môže trvať až
čas úmerný počtu kľúčov. Toto sa dá riešiť na úkor pamäte udržiavaním istej
predpočítanej množiny vrcholov. Druhá možnosť je, ak chceme používať kľúče
zaradom v podarí $1,2,\dots,n$, potom existujú isté algoritmy na iteratívne
počítanie, kedy z autentifikačnej cesty pre kľúč $k$ vypočítame cestu pre
kľúč $k+1$ v čase aj pamäti $O(\log n)$, napríklad podľa \cite{merkle_iter}.

Viac o Merkleho stromoch a iných vylepšeniach Lamportovej schémy
možno nájsť v \cite{merkle}.

\subsection{Využitie Merkleho stromov pri extrakcii textu}

Uvažujme nasledujúci setting -- máme ústavu SR, čo je veľký dokument, ktorý
sa dá stiahnuť. Samozrejme, existuje verejný podpis tohoto dokumentu, aby
sme si mohli overiť, že nám niekto nepozmenil výklad niektorých paragrafov.
To znamená, že keď mám celý dokument, môžem si overiť jeho autentickosť.
Problém je zrejmý -- dokument je príliš dlhý a celý nás pravdepodobne
nezaujíma. Nás zaujíma iba nejaký konkrétny zákon alebo paragraf. Lenže na
to, aby sme mohli overiť, že daný paragraf je naozaj autentický, musíme
stiahnuť aj zvyšok dokumentu. Toto je samozrejme veľmi neefektívne. Preto
hľadáme spôsob, akým môžeme efektívne digitálne podpísať dokument a pritom
umožniť overovanie jednotlivých podčastí (napríklad celé zákony alebo
paragrafy). Na druhej strane, nechceme povoliť aby sa dala overiť iba
nejaká časť zákona. Čo kebyže nám tak niekto úmyselne zatají nejakú
dôležitú časť na konci. Na takéto účely sa preto konštruuje takzvaný
zovšebecnený Merkleho strom, ktorý umožnuje overovať iba niektoré
časti dokumentu.
Ak čitateľa zaujala táto problematika, odporúčame prečítať publikáciu
doc. Martina Staneka \cite{stanek}.

\subsection{Fail-stop podpisové schémy}

Predstavme si, že chceme schému pri ktorej sme (ako podpisovateľ) chránený pred neobmedzene výpočtovo silným
falšovateľom. Inak povedané, žiadny útočník, nech je akokoľvek silný,
by nemal z prístupu k môjmu verejnému kľúču byť schopný generovať
platné podpisy. Toto je samozrejme mierne v rozpore s tým, že máme
vedieť overiť podpis. Preto budeme požadovať miernejšiu vec --
podpisovateľ bude schopný preukázať, že to nebolo podpísané jeho
súkromným kľúčom.
Opäť si predstavíme jednorázovú schému. Útočník v prípade získania
správy, jej podpisu a verejného kľúča nebude schopný identifikovať
jednoznačne súkromný kľúč (napríklad preto, že možných súkromných
kľúčov bude veľmi veľa)
a nebude schopný vyrobiť správny podpis inej správy.
Pokiaľ sa falšovateľ pokúsi podpisať inú správu, tak podpisovateľ zistí, že bol použitý iný
ako jeho súkromný kľúč a je to schopný preukázať.

\subsubsection{Heyst-Pedersenova schéma}

Uvažujme grupu $G$, kde $|G| = q$ a $q$ je nejaké (dostatočne veľké) prvočíslo.
Zoberme generátory $g, h \in G$.
Súkromný kľúč bude štvorica  
$sk = \langle x_1, x_2, y_1, y_2 \rangle \inr Z_q^4$.
Poznamenajme, že narozdiel od ElGamalovej schémy, hodnoty $x,y$ sú
náhodné a \emph{nezávislé}.
Verejný kľúč bude štvorica 
$pk = \langle g,h, g^{x_1} h^{x_2},\ g^{y_1} h^{y_2} \rangle = 
    \langle g,h,z_1, z_2 \rangle$, teda akýmsi
spôsobom previažeme obe hodnoty. Algoritmický zápis generovania je vo
funkcii \ref{funct:genhp}.

\begin{function}[h!]
    \caption{GenHP($G$)}
    \label{funct:genhp}
    $g,h \assign $ rôzne generátory $G$\;
    $x_1,x_2,y_1,y_2 \inr G$\;
    $z_1 \assign g^{x_1} h^{x_2}$\;
    $z_2 \assign g^{y_1} h^{y_2}$\;
    \Return $sk=\langle x_1,x_2,y_1,y_2 \rangle,\ 
        pk=\langle g,h,z_1,z_2 \rangle$\;
\end{function}

Správu $m$ podpíšeme svojim súkromným kľúčom ako lineárnu kombináciu
$m,x_i, y_i$ pomocou funkcie \ref{funct:signhp}.

\begin{function}[h!]
    \caption{SignHP($m$)}
    \label{funct:signhp}
    $\sigma_1 \assign x_1 + m y_1$\;
    $\sigma_2 \assign x_2 + m y_2$\;
    \Return $\sigma=\langle \sigma_1,\sigma_2 \rangle$\;
\end{function}

Overenie podpisu je jednoduché otestovanie
rovnosti:
\begin{function}[h!]
    \caption{VerifyHP($m,\sigma,pk$)}
    \eIf{$g^{\sigma_1} h^{\sigma_2} == z_1 z_2^m$}{
        \Return accept\;
    }{
        \Return reject\;
    }
\end{function}

Teraz si dokážeme niekoľko vlastností tejto schémy.

\begin{lema}
    Pre ľubovoľnú trojicu $\langle pk, m, \sigma \rangle$,
    kde $\sigma = SigHP_{sk}(m)$
    a $sk$ je nejaký vyhovujúci súkromný kľúč
    existuje $q$ rôznych kľúčov $sk^*$, takých že $\sigma = Sig_{sk^*}(m)$.
\end{lema}

\begin{dokaz}
    Nech $h = g^a$, $z_1 = g^{e_1}$ a $z_2 = g^{e_2}$ 
    (neobmedzene silný útočník vie $a, e_1, e_2$ vypočítať).
    Z~toho, že $z_1 = g^{x_1} h^{x_2}$ máme rovnicu $e_1 = x_1 + ax_2$.
    Podobne z rovnice $z_2 = g^{y_1} h^{y_2}$ dostaneme $e_2 = y_1 + a y_2$.
    A ešte vďaka tomu, že $\sigma$ je podpis správy $m$ máme rovnice
    $\sigma_1 = x_1 + my_1$, $\sigma_2 = x_2 + my_2$. 

    Dostali sme 4 rovnice. Máme 4 neznáme. V maticovom tvare dostávame:
    \begin{equation*}
    %%% {{{
        \left ( \begin{matrix}
                    1 & a & 0 & 0 \\
                    0 & 0 & 1 & a \\
                    1 & 0 & m & 0 \\
                    0 & 1 & 0 & m
                \end{matrix}
        \right )
        \left ( \begin{matrix}
                    x_1 \\
                    x_2 \\
                    y_1 \\
                    y_2
                \end{matrix}
        \right )
        =
        \left ( \begin{matrix} 
                    e_1 \\
                    e_2 \\
                    \sigma_1\\
                    \sigma_2
                \end{matrix}
        \right )
    %%% }}}
    \end{equation*}

    Matica sústavy má ale hodnosť $3$. Jedno riešenie už máme (pôvodný
    súkromný kľúč) a teda sústava má práve $q$ rôznych riešení (sme v
    priestore $Z_q^4$).
\end{dokaz}

Toto dokazuje, že ak získame správu $m$ a jej podpis $\sigma$,
potenciálnych súkromných kľúčov je exponenciálne veľa (práve $q$).
Na to aby sme ukázali, že útočník má šancu na úspech $1/q$ 
treba ešte ukázať jednu vec.
Útočník totiž chce vytvoriť novú správu $m^*$ a jej podpis $\sigma^*$.
Čo ak by sa stalo, že síce zo správy $m$ a jej podpisu $\sigma$
získame veľa rôznych súkromných kľúčov, avšak existovala by správa
$m^*$, pri ktorej by použitie týchto kľúčov viedlo k rovnakému podpisu 
$\sigma^*$? Je to veľmi nepríjemný prípad, kedže potom šanca na
vygenerovanie korektného a nevyvrátiteľného podpisu je vyššia ako by
sme chceli.
Formálne popísané, nechceme aby nastal prípad, že máme sadu možných súkromných
kľúčov $sk_1, sk_2, \dots, sk_n$, pre ktoré platí
$Sig_{sk_1}(m^*) = Sig_{sk_2}(m^*) = \dots = Sig_{sk_n}(m^*)$.
To, že tento prípad nenastane ukazuje nasledujúca lema:

\begin{lema}
    Pre ľubovoľné $\langle pk, m, \sigma, m^*, \sigma^* \rangle$, kde
    súkromný kľúč $sk$ vyhovuje verejnému kľúču $pk$ a platí
    $\sigma = Sig_{sk}(m)$, $\sigma^* = Sig_{sk}(m^*)$ platí,
    že existuje existuje maximálne jeden takýto kľúč $sk$.
\end{lema}

\begin{dokaz}
    Prvé 4 rovnice máme rovnaké ako v predchádzajúcej leme.
    Navyše dostaneme ešte dve rovnice: $x_1 + m^*y_1 = \sigma_1^*$ a
    $x_2 + m^* y_2 = \sigma_2^*$.
    Pokiaľ zostrojíme maticu tejto sústavy bude mať hodnosť $4$ 
    a teda bude mať maximálne jedno riešenie.
\end{dokaz}


Ešte treba vyriešiť otázku ako môže podpisujúci spochybniť podpis 
a či tomuto spochybneniu môžeme veriť.
Keďže je to jednorázová schéma, podpisujúcemu v prípade,
že chce spochybniť podpis, stačí ak zverejní vlastný súkromný kľúč.
V tom prípade vieme overiť, že nesedí s podpisom falošnej správy
a navyše vyhovuje verejnému kľúču. Toto na druhú stranu
umožňuje poprieť vlastný podpis, ak máme dostatočne veľkú výpočtovú
silu.

Ukážeme ešte, že podpisujúci si nevie vymyslieť iný súkromný kľúč
(samozrejme ak je výpočtovo obmedzený). 
Nech jeho pôvodný súkromný kľúč je 
$sk = \langle x_1, x_2, y_1, y_2 \rangle$ a
chce si pripraviť nový kľúč
$sk^{'} = \langle x_1', x_2', y_1', y_2' \rangle$.
Potom platí $z_1 = g^{x_1} h^{y_1} = g^{x_1'} h^{y_1'}$ z čoho máme 
$h = g^{(x_1 - x_1')(y_1' - y_1)^{-1}}$.
A teda vieme zistiť $\dlog_g h$.

\begin{poznamka}
    Posledná časť bola odprednášaná mierne inak (cez rovnosť
    podpisov), nám sa ale zdal tento prístup priamejší.
\end{poznamka}
